The present invention generally relates to techniques for decoding of communication signals that have been encoded using convolutional coding. More particularly, the invention pertains to improvements in decoding signals that have been encoded using a coding technique generally known as trellis coded modulation (TCM). Communication of data through digital communication channels is subject to well known limitations. For communication channels involving orbiting satellites, there is an inherent transponder power limitation, given that a satellite must rely on batteries and solar power. In addition, rapid growth in data rate requirements have resulted in significant bandwidth limitations. Every communication channel is, of course, subject to unwanted noise interference. The effects of noise can be mitigated by employing higher transmitted power and greater bandwidth, but in a practical digital communication channel power and bandwidth are limited, so communication engineers have developed various techniques to correct digital data streams affected by noise. One measure of transmission channel performance is its transmission efficiency, measured in bits per second per Hertz, that is, the data transmission rate in bits per second, for each Hertz of bandwidth.
A widely accepted technique for increasing transmission efficiency is known as forward error correcting (FEC) coding. In essence, the principle of FEC coding is to generate redundancy in the data stream to be transmitted, such that each bit of data has an influence on the state of other adjacent bits of transmitted code. Given this inherent redundancy in the transmitted code stream, a receiver with an appropriate decoder can not only decode the received data but can correct errors in the received data based on reconstruction of the data using redundant information from adjacent bits. A detailed explanation, and even a simple example, of FEC coding is much more complicated than this simple statement of the principle.
FEC coding is often effected by means of a convolutional encoder, which, in its simplest form is a shift register and combinatorial logic that combines the binary states of selected stages of the shift register. The logic typically takes the form of exclusive-OR gates, each of which performs a modulo-two addition of its input bits. Data bits from each shift register stage are clocked not only to the next stage but into selected ones of the logic gates. Output data is clocked from selected logic gates. The rate of a convolutional encoder is defined as the ratio of its number of inputs to its number of outputs. For example, a convolutional encoder with two outputs for every input is referred to as a rate 1/2 encoder. Convolutional encoders may be designed to operate at other rates, such as 3/4, 4/5 and so forth. A convolutional encoder is also defined in part by its “constraint length,” which is defined as the number of output bits affected by a given input bit (typically this value is one more than the number of shift register stages in the encoder) and by code generator polynomials. These may be expressed as binary or octal numbers that define the shift register connections to the modulo-two adders of the encoder.
A convolutional encoder may also be conveniently thought of as a state machine that changes state in response to a stream of input data bits. Consideration of the various changes of state that can occur in response to a data stream gives rise to a convenient graphical representation of the state machine, known as a trellis diagram. A trellis diagram is a rectangular matrix of dots. Each dot in the same row represents the same state, for example state 00, state 01, state 10, or state 11. Each column of dots represents possible states at a particular time instant. In a trellis diagram, if all possible state transitions from one time instant to the next are represented by diagonal or horizontal lines from one column of dots to the next, the result is a criss-cross pattern that resembles a trellis.
The trellis diagram format may also be used to depict the actual state transitions of a convolutional encoder when encoding a specific data stream. In this case, the diagram less resembles a trellis but shows in graphical form the succession of states assumed by the encoder during the encoding of a series of input data bits. The trellis diagram is key to understanding the decoding technique originally developed by Andrew J. Viterbi and referred to as Viterbi decoding. Encoding digital data convolutionally in the manner briefly described above and mapping the bit values onto an expanded signal constellation so that the free Euclidean distance is maximized is the essence of trellis coded modulation (TCM).
It will be appreciated that, even in a simple case of an encoder using just a few stages, the trellis diagram is computationally complex. A more useful encoder would have a larger constraint length, such as seven, and the encoder would have 26 or 64 states. The corresponding trellis diagram and the Viterbi decoding algorithm are complex and cumbersome in the extreme. Efforts to simplify TCM decoding led to a method known as pragmatic trellis-coded modulation (PTCM), described in a paper by Andrew J. Viterbi et al., entitled “A Pragmatic Approach to Trellis-Coded Modulation,” July 1989 IEEE Comm. Magazine, pp. 11-19.
The design of TCM encoders and decoders for optimum performance depends in part on the type of data modulation employed. The PTCM technique proposed in the Viterbi et al. paper is an approach that permits a single basic encoder and decoder using a rate of 1/2 and a constraint length of seven, to be applied to various modulation schemes. Digital modulation schemes using phase and/or amplitude modulation are generally defined by signal constellations, i.e., graphical representations of the possible signal phases and amplitudes used to represent various data states. The PTCM technique is said to be applicable to a wide variety of signal constellations. Prior to the Viterbi et al. paper, G. Ungerboeck showed in a paper entitled “Channel Coding with Multilevel/Phase Signals,” IEEE Trans. on Info. Theory, vol IT-28, pp. 55-67, January 1982, that it was possible to achieve Asymptotic Coding Gains (ACGs) of as much as 6 dB within precisely the same signal spectral bandwidth, by doubling the signal constellation set from M=2k−1 symbols to M=2k symbols, employing a rate (k−1)/k convolutional code, and mapping the bits onto the signal constellation in such a way that the free Euclidean distance of the resulting trellis was maximized. The Viterbi et al. paper pointed out that there were a number of drawbacks to the Ungerboeck approach, as subsequently refined by others. First, each signal configuration seemed to require a different convolution code, and no single encoder-decoder could be used for a wide set of parameters. Second, the Ungerboeck approach suffered from the practical limitation that the number of trellis code states used in most application was very low, typically four or eight, and rarely more than sixteen. Finally, performance in the Ungerboeck model was always to be measured by ACG, which is a function of free Euclidean distance. Viterbi et al. believed that using free Euclidean distance to measure performance would lead to misleading results because not only may there be a large number of paths at the same distance, but also the next higher Euclidean distance between unmerged paths may be only a very small amount larger than the free distance.
In summary, Ungerboeck determined the optimal convolutional code for several TCM modulation types. Then, Viterbi et al. showed that in most cases the de facto industry standard encoder (with constraint length 7, rate 1/2 and generator polynomials 1718 and 1338) could be used along with a technique known as “puncturing” to perform the convolutional coding with little or no loss in bit error rate (BER) performance in many situations. In the puncturing technique, selected bits of the encoder output stream are discarded, resulting in a higher effective code rate. For example, if one output bit in every four from a rate 1/2 encoder is discarded, the encoder effectively outputs three bits for every two input bits and effectively functions as a 2/3 encoder. If two bits of each group of six output bits are discarded, the encoder produces four output bits for each set of three input bits and effectively functions as a 3/4 encoder. When the encoded data stream is punctured in this manner, the data stream received and decoded must be “de-punctured” to supply the discarded data. Typically, de-puncturing is effected by inserting median values that do not affect the decoding process.
Although PTCM decoding techniques represent a practical advantage over earlier convolution encoding and decoding methods, puncturing and de-puncturing the code necessarily results in diminished BER performance. A return to the earlier approach of performing a “full-rate” trellis decoding operation, without puncturing and de-puncturing of the code, presents an extraordinary increase in computational complexity, even at the standard constraint length of seven bits. Accordingly, it would be highly advantageous to provide a convolutional encoding and decoding approach that retains the simplifying advantages of the PTCM approach, but does not result in lowering of the BER performance. The present invention is directed to this end.